1. Field of the Invention
The present invention relates to elliptic curve arithmetic operation techniques and elliptic curve application techniques.
2. Description of the Prior Art
In recent years, the use of elliptic curves is becoming popular in the encrypted communications technology. Cryptosystems that employ elliptic curves rely for their security on the difficulty of solving a discrete logarithm problem.
Representative examples of the discrete logarithm problem are problems based on finite fields and problems based on elliptic curves. Such problems are described in detail in Neal Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag (1987).
(Elliptic Curve Discrete Logarithm Problem)
The elliptic curve discrete logarithm problem is the following.
Let E(GF(p)) be an elliptic curve defined over a finite field GF(p), with a point G on the elliptic curve E, given when the order of E is divisible by a large prime, being set as a base point. Here, “the order of the elliptic curve” means the number of points on the elliptic curve whose coordinates are in GF(p). This being so, the problem is to find an integer x such thatY=xGwhere Y is a given point on E, if such an integer x exists.
Here, p is a prime and GF(p) contains p elements.
(Conditions for Secure Elliptic Curves)
Given that various cryptanalysis attacks against elliptic curve discrete logarithm problems have been devised over the years, it is of great importance to construct a secure elliptic curve to strengthen the elliptic curve cryptosystem against these attacks.
In this specification, “constructing an elliptic curve” roughly means to determine the parameters a and b of an elliptic curve which is given by an equationy^2=x^3+ax+bwhere the sign ^ represents a repeated multiplication, such as x^3=x×x×x.
To be secure against all existing cryptanalysis attacks, an elliptic curve over the finite field GF(p) must satisfy the conditions:
(a) the order of the elliptic curve is not equal to any of p−1, p, and p+1; and
(b) the order of the elliptic curve has a large prime factor.
In other words, checking the order of the elliptic curve allows the security of the elliptic curve to be assessed.
According to T. Okamoto & K. Ohta Encryption, Zero Knowledge Proof, and Number Theory, Kyoritsu (1995), pp.155˜156, when the above conditions are satisfied, computation time required to solve the elliptic curve discrete logarithm problem is exponential time in the largest prime factor of the elliptic curve order.
(Methods of Constructing Elliptic Curves)
There are mainly two elliptic curve construction methods that are:
{circle around (1)} elliptic curve construction using the CM (Complex Multiplication) method; and
{circle around (2)} elliptic curve construction using an order computation algorithm.
Although {circle around (1)} can construct an elliptic curve easily, it cannot choose an elliptic curve at random. For details of this method, see A. Miyaji “On Ordinary Elliptic Curve Cryptosystems” ASIACRYPT'91, Springer-Verlag (1991), pp.460˜469. Meanwhile, {circle around (2)} can construct a random elliptic curve, though it takes considerable time to do so.
(Prior Art Example 1: Elliptic Curve Construction using an Order Computation Algorithm)
The following introduces the method of constructing an elliptic curve using an algorithm to compute the order of the elliptic curve, with reference to FIG. 1. For details on this method, see N. Koblitz “Elliptic Curve Implementation of Zero-Knowledge Blobs” J. Cryptology, vol.4, no.3 (1991), pp.207˜213.
First, a random number is generated (S901), and parameters which define the elliptic curve are generated using the random number (S902). Next, the order of the elliptic curve is computed using the generated parameters (S903). The computed order is checked whether it satisfies one or more predetermined conditions for secure elliptic curves, to assess the security of the elliptic curve (S904). If and only if the order satisfies the conditions, the generated elliptic curve parameters are outputted. If the order does not satisfy the conditions, the procedure returns to step S901 to repeat the random number generation, the parameter generation, the order computation, and the security judgement, until an elliptic curve whose order satisfies the conditions in step S904 is found.
This method which employs an order computation algorithm requires long computation time. Especially, it takes much time to compute the order of the elliptic curve.
One example of algorithms used to compute orders of elliptic curves is an algorithm proposed by Schoof. This algorithm is a polynomial time algorithm. The polynomial time algorithm referred to here is an algorithm whose computation time is polynomial time. The computation time of Schoof's algorithm per se is not practical.
(Prior Art Example 2: Elliptic Curve Order Computation According to the SEA Algorithm)
Atkin and Elkies have proposed several improvements of Schoof's algorithm and so have designed the SEA (Schoof-Elkies-Atkin) algorithm.
This algorithm is detailed in R. Lercier & F. Morain “Counting the Number of Points on Elliptic Curves over Finite Fields: Strategies and Performances” EUROCRYPT'95, Springer-Verlag (1995), pp.79˜94.
The SEA algorithm computes t mod L^n (n=1, 2, 3, . . . ). This can be done by calculating an eigenvalue of a map called the Frobenius map. More specifically, k is found from an equation(α^p,β^p)=k(α,β)where (α,β) is an L-division point on an elliptic curve E and k(α,β) is a point on E after exponentiating the point (α,β) by k. This is carried out through computation on the elliptic curve E on a residue class ring of polynomials in variable α and β with elements of GF(p) as coefficients, the moduli of the ring being polynomials β^2−f(α) and h(α). Computational complexity of the inversion of a polynomial is greater than computational complexity of the multiplication of a polynomial, so that a 3-tuple coordinate is used in this computation. Here, projective coordinate is employed as the 3-tuple coordinate, as the projective coordinate has been conventionally used for elliptic curves over finite fields. Conventional projective coordinate is described in Miyaji, Ono & Cohen “Efficient Elliptic Curve Exponentiation” Advances in Cryptology-Proceedings of ICICS'97, Lecture Notes in Computer Science, Springer-Verlag (1997), pp.282-290.(Prior Art Example 3: Calculation of the Exponentiation Point k(α,β) on the Elliptic Curve E)
Exponentiating the point (α,β) on the elliptic curve E by k is done by splitting the exponentiation into additions and doublings and performing the additions and the doublings in the following way.
Suppose (α,β) is transformed to (α:β:1), and (α:β:1) is interpreted as (X(α):β×Y(α):Z(α)) (where X(α)=α and Y(α)=Z(α)=1).
Note here that “(,)” and “(: :)” represent affine coordinates and protective coordinates, respectively.
AssumeP1=(X1(α):β×Y1(α):Z1(α))P2=(X2(α):β×Y2(α):Z2(α))P3=P1+P2=(X3(α):β×Y3(α):Z3(α))
In this specification, the operators × and * in an addition formula or a doubling formula both denote a multiplication. In the addition formula or the doubling formula, a multiplication which appears for the first time in the formula is expressed by the operator *, whereas a multiplication which has already appeared is expressed by the operator ×. The number of multiplications in the addition or doubling formula can be obtained by counting the number of operators * in the formula.
(1) Addition Formula
When P1≠±P2, addition is required, the formula of which isX3=v*AY3=u*(v^2×X1×Z2−A)−v^3*(Y1×Z2)Z3=v^3*(Z1×Z2)where u=Y2*Z1−Y1*Z2v=X2*Z1−X1*Z2                    A        =                ⁢                                            u              ^              2                        ×                          f              ⁡                              (                α                )                                      ×            Z1            ×            Z2                    -                      v            ^            3                    -                      2            ×                          v              ^              2                        ×            X1            ×            Z2                                                  =                ⁢                                            (                                                (                                      u                    *                    u                                    )                                *                                  f                  ⁡                                      (                    α                    )                                                              )                        *                          (                              Z1                *                Z2                            )                                -                                    (                              v                *                v                            )                        *            v                    -                      2            ×                          v              ^              2                        *                          (                              X1                ×                Z2                            )                                          andf(x)=x^3+ax+b
It is to be noted that, although X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3, u, v, and A are polynomials in the variable α and therefore should be written like X1(α), Y1(α), and Z1(α) to be precise, (α) has been omitted here for convenience in writing.
(2) Doubling Formula
When P1=P2, doubling is required, the formula of which is                     X3        =                ⁢                  2          ×          h          *                      (                          s              ×                              f                ⁡                                  (                  α                  )                                                      )                                                  Y3        =                ⁢                              w            ×                          (                                                4                  ×                  B                                -                h                            )                                -                      8            ×                          Y1              ^              2                        ×                          s              ^              2                        ×                                          f                ⁡                                  (                  α                  )                                            ^              2                                                              =                ⁢                              w            *                          (                                                4                  ×                  B                                -                h                            )                                -                      8            ×                          (                              Y1                ×                s                ×                                  f                  ⁡                                      (                    α                    )                                                              )                        *                          (                              Y1                ×                s                ×                                  f                  ⁡                                      (                    α                    )                                                              )                                                              Z3        =                ⁢                  8          ×                      s            ^            3                    ×                                    f              ⁡                              (                α                )                                      ^            2                                                  =                ⁢                  8          ×          s          *                      (                          s              ×                              f                ⁡                                  (                  α                  )                                                      )                    *                      (                          s              ×                              f                ⁡                                  (                  α                  )                                                      )                              where                     w        =                ⁢                              a            ×                          Z1              ^              2                                +                      3            ×                          X1              ^              2                                                              =                ⁢                              a            ×                          (                              Z1                *                Z1                            )                                +                      3            ×                          (                              X1                *                X1                            )                                                              s        =                ⁢                  Y1          *          Z1                                        B        =                ⁢                  X1          *                      (                          Y1              *                              (                                  s                  *                                      f                    ⁡                                          (                      α                      )                                                                      )                                      )                                                  h        =                ⁢                              w            ^            2                    -                      8            ×            B                                                  =                ⁢                              w            *            w                    -                      8            ×            B            ⁢                                                   ⁢            and                                                            f          ⁡                      (            x            )                          =                ⁢                              x            ^            3                    +                      a            ⁢                                                   ⁢            x                    +          b                    
As with the addition formula, though X1, Y1, Z1, X3, Y3, Z3, w, s, B, and h are polynomials in the variable α, (α) is omitted for convenience in writing.
The number of multiplications is 15 in the addition formula and 12 in the doubling formula, as can be seen from the number of operators * in each of the formulas. When computational complexity of a polynomial multiplication is measured as 1×PMul, the computational complexity of the addition is 15×PMul and the computational complexity of the doubling is 12×PMul.
In counting the number of multiplications, computational complexity of multiplying a constant and a polynomial, such as a×(Z1^2) or 3×(X1^2), is smaller than computational complexity of multiplying a polynomial and a polynomial, so that such a multiplication is ignored in the counting. Likewise, a multiplication which has once appeared does not have to be calculated again because the previous multiplication result can be used, so that such a multiplication is ignored in the counting.
(Prior Art Example 4: Elliptic Curve Construction Based on the SEA Algorithm)
A method of constructing elliptic curves using the SEA algorithm is proposed in pp. 379˜392 in R. Lercier “Finding Good Random Elliptic Curves for Cryptosystems Defined over F(2^n)” Advances in Cryptology-Proceedings of EUROCRYPT'97, Lecture Notes in Computer Science, 1233, Springer-Verlag (1997) (hereinafter referred to as “document 1”). In this method the predetermined conditions used in the elliptic curve construction of prior art example 1 are defined as “the order of the elliptic curve is a prime”.
Lercier's elliptic curve construction method which employs the SEA algorithm is described below with reference to FIGS. 2 and 3.
Let p be a prime which is an input value. Also, let E be an elliptic curve over a finite field GF(p) and E′ be the quadratic twist of E. Then there is the relationship that, if the order of E is p+1−t, the order of E′ is p+1+t.
First, an element u of the finite field GF(p) is chosen at random (S931), and parameters of the elliptic curve E are determined based on the element u (S932). Then, flags flag#ell and flag#twist are both set at an initial value 1 (S933).
Next, the order of E and the order of E′ are calculated according to the SEA algorithm (S934).
If the order of E is divisible by L (S935), flag#ell is changed to 0 (S936), whereas if the order of E′ is divisible by L (S937), flag#twist is changed to 0 (S938). When flag#ell=0 and flag#twist=0 (S940), the procedure returns to step S931. Otherwise, the procedure proceeds to step S941.
When flag#ell=1 (S941), it is judged whether the order of E is prime (S942). If the order of E is prime, the procedure proceeds to step S945. If the order of E is not prime, it is judged whether flag#twist=1 (S943). When flag#twist≠1, the procedure returns to step S931. When flag#twist=1, it is judged whether the order of E′ is prime (S944). If the order of E′ is not prime, the procedure returns to step S931. If the order of E′ is prime, the procedure proceeds to step S945.
It is judged in step S945 whether the order of E is equal to p. If the order is equal to p, the procedure returns to step S931. If the order is not equal to p, the parameters of the elliptic curve E are outputted (S946).
In Lercier's elliptic curve construction, step S933 is used to accelerate computation, thereby reducing computation time needed for the SEA algorithm. Nevertheless, since in step S932 the parameters of the elliptic curve E are determined without consideration given to the possibility that the order of the elliptic curve E is not prime, the order computation according to the SEA algorithm in step S934 may have to be repeated again and again. This causes an increase in overall computational complexity.
Thus, despite the fact that Schoof's order computation algorithm in elliptic curve construction has been modified as the SEA algorithm and improvements to reduce computational complexity of the SEA algorithm have been proposed by Lercier, there still remains the demand to further reduce computational complexity for elliptic curves.